Cryptographic systems are widely used to insure the privacy and authenticity of messages communicated over insecure channels. In many applications, it is necessary that encryption be performed at high data rates, a requirement usually achieved, if at all, with the help of supporting cryptographic hardware. Such hardware, however, is not available on most conventional computer systems. Moreover, even when cryptographic hardware is available, it has been found that an algorithm designed to run well in hardware does not perform in software as well as an algorithm optimized for software execution. The hardware-efficient algorithm of the Data Encryption Standard (DES) is no exception.
Prior attempts to design encryption methods for efficient implementation in software are known in the prior art. Several of these functions are described in U.S. Pat. No. 5,003,597 and in the article entitled "Fast Software Encryption Functions", R. Merkle, Advances in Cryptology, CRYPTO '90 Proceedings, Springer-Verlag. In general, the Merkle technique constructs a fixed length or "block" cipher by operating upon a data input having two halves: a left half and a right half. The left half is used as an index to access a table of pseudorandom numbers to thereby retrieve a table value. That value is then exclusively ORed (XOR) with the right half of the data input and the result relabeled as the left half. The original left half is then rotated by a predetermined amount and relabeled as the right half. The iterative process is then continued in this fashion until the data input is fully randomized. To achieve high speed, in one embodiment the table of pseudorandom numbers is precomputed.
The Merkle technique and other known software-oriented block ciphers provide advantages over prior art hardware-based encryption techniques. Nevertheless, there remains a need to provide improved software-efficient encryption techniques that exhibit high speed and computational efficiency on conventional processor platforms.